#include "ArbolHuffman.h"
#include <iostream>
#include <string>

using namespace std;

ArbolHuffman::ArbolHuffman() {
	this->nyt = new NodoArbolHuffman(0, 512, 0); // Nodo NYT de frecuencia 0
	this->raiz = this->nyt;
	this->nodosOrdenados = new ListaDeNodosOrdenados();
	this->nodosOrdenados->agregarNodo(this->raiz);
}

// Recibe un caracter y emite su código. Actualiza el arbol
unsigned int ArbolHuffman::codificarCaracter(const char caracter) {
	cout << "Leo caracter '" << caracter << "'." << endl;
	// Busco en nodosOrdenados pero tambien se podria buscar en el arbol
	NodoArbolHuffman* nodoConCaracter = 0;
	if ((nodoConCaracter = this->nodosOrdenados->buscarCaracter(caracter)) != 0)
	{
		cout << "No es la primera vez que aparece '" << caracter << "'." << endl;
		this->enviarCodigo(nodoConCaracter);
		this->actualizar(nodoConCaracter);
	} else {
		cout << "Es la primera vez que aparece '" << caracter << "'." << endl;
		cout << "Envio codigo NYT:" << endl;
		this->enviarCodigo(this->nyt);
		cout << "Envio caracter sin codificar: '" << caracter << "'." << endl;
		this->actualizarCaracterNuevo(caracter);
	}
	return 0; //TODO: Esto tiene que devolver el codigo del caracter
}

// Recorre el arbol desde la raiz hasta el nodo y manda el código (al reves).
void ArbolHuffman::enviarCodigo(NodoArbolHuffman* nodo) {
	string codigo = "";
	if (nodo != this->raiz) {
		do {
			if (nodo->getPadre()->getHijoDerecha() == nodo) {
				codigo += "1";
			} else {
				codigo += "0";
			}
			nodo = nodo->getPadre();
		} while (nodo != this->raiz);
	}
	 // TODO: Hay que dar vuelta el string.
	 // De alguna manera hay que hacer que este codigo se transforme en 1s y 0s en bits.
	 cout << "Codigo: " << codigo << endl;
}

// Agrega un nuevo caracter al arbol. Deja el arbol valido.
void ArbolHuffman::agregarCaracter(char caracter) {
	// Creo dos hojas (la del nuevo caracter y la del nuevo NYT)
	// cuyo padre es el viejo nodo NYT
	cout << "Agrego '"<< caracter << "' al arbol." << endl;
	this->nyt->setHijoIzquierda(new NodoArbolHuffman(this->nyt, this->nyt->getNumero()-2, 0));
	this->nyt->setHijoDerecha(new NodoArbolHuffman(this->nyt, this->nyt->getNumero()-1, caracter));
	this->nodosOrdenados->agregarNodo(this->nyt->getHijoDerecha());
	this->nodosOrdenados->agregarNodo(this->nyt->getHijoIzquierda());
	this->nyt->incrementarFrecuencia();
	this->nyt->getHijoDerecha()->incrementarFrecuencia();
	this->nyt = this->nyt->getHijoIzquierda();
}

// Actualiza el árbol a partir del caracter NYT
// Deja el arbol en un estado valido (Sibling property)
void ArbolHuffman::actualizarCaracterNuevo(char caracter) {
	this->agregarCaracter(caracter);
	NodoArbolHuffman* nodo = this->nyt->getPadre(); // NYT anterior
	while (nodo != this->raiz) {
		nodo = nodo->getPadre();
		NodoArbolHuffman* nodoMaxFrecuenciaEnBloque = this->nodosOrdenados->buscarMaxEnBloque(nodo->getFrecuencia());
		if ((nodoMaxFrecuenciaEnBloque != nodo) && (nodoMaxFrecuenciaEnBloque != nodo->getPadre())) {
			// Intercambio de nodos para poder incrementar la frecuencia luego
			// y que siga cumpliendo con la Sibling Property
			this->intercambiarNodos(nodo, nodoMaxFrecuenciaEnBloque);
		}
		nodo->incrementarFrecuencia();
	}
}

// Actualiza el árbol a partir de un nodo al que hay que incrementarle su frecuencia
// Deja el arbol en un estado valido (Sibling property)
void ArbolHuffman::actualizar(NodoArbolHuffman* nodo) {
	NodoArbolHuffman* nodoMaxFrecuenciaEnBloque = this->nodosOrdenados->buscarMaxEnBloque(nodo->getFrecuencia());
	if ((nodoMaxFrecuenciaEnBloque != nodo) && (nodoMaxFrecuenciaEnBloque != nodo->getPadre())) {
		// Intercambio de nodos para poder incrementar la frecuencia luego
		// y que siga cumpliendo con la Sibling Property
		this->intercambiarNodos(nodo, nodoMaxFrecuenciaEnBloque);
	}
	nodo->incrementarFrecuencia();
	while (nodo != this->raiz) {
		nodo = nodo->getPadre();
		NodoArbolHuffman* nodoMaxFrecuenciaEnBloque = this->nodosOrdenados->buscarMaxEnBloque(nodo->getFrecuencia());
		if ((nodoMaxFrecuenciaEnBloque != nodo) && (nodoMaxFrecuenciaEnBloque != nodo->getPadre())) {
			// Intercambio de nodos para poder incrementar la frecuencia luego
			// y que siga cumpliendo con la Sibling Property
			this->intercambiarNodos(nodo, nodoMaxFrecuenciaEnBloque);
		}
		nodo->incrementarFrecuencia();
	}
};

// Intercambia dos nodos de igual frecuencia
void ArbolHuffman::intercambiarNodos(NodoArbolHuffman* nodo, NodoArbolHuffman* nodoMaximo) {
	this->nodosOrdenados->intercambiarNodos(nodo->getNumero(), nodoMaximo->getNumero());
	NodoArbolHuffman* nodoPadre;
	nodoPadre = nodo->getPadre();
	NodoArbolHuffman* nodoPadreMaximo;
	nodoPadreMaximo = nodoMaximo->getPadre();
	if (nodoPadre->getHijoIzquierda() == nodo)
	{
		nodoPadre->setHijoIzquierda(nodoMaximo);
	} else {
		nodoPadre->setHijoDerecha(nodoMaximo);
	}
	nodoMaximo->setPadre(nodoPadre);
	if (nodoPadreMaximo->getHijoDerecha() == nodoMaximo) {
		nodoPadreMaximo->setHijoDerecha(nodo);
	} else {
		nodoPadreMaximo->setHijoIzquierda(nodo);
	}
	nodo->setPadre(nodoPadreMaximo);
	// Ahora quiero intercambiar los numeros de los nodos
	unsigned int numeroTemp = nodo->getNumero();
	nodo->setNumero(nodoMaximo->getNumero());
	nodoMaximo->setNumero(numeroTemp);
}

int main() {
	ArbolHuffman* arbol = new ArbolHuffman();
	string str="estoy probando el arbol de huffmanhecho en c++ para ver que onda";
	for(int x=0;x<str.length();x++)
		arbol->codificarCaracter(str[x]);
	return 0;
}
